Technical Field
Embodiments of the present disclosure are directed to methods of forming error correcting codes.
Discussion of the Related Art
In coding theory, BCH codes form a class of cyclic error-correcting codes (ECCs) that are constructed using finite fields. BCH codes are named for their inventors Raj Bose, D. K. Ray-Chaudhuri, and Alexis Hocquenghem. BCH codes can be defined as follows. For a correction radius t, the primitive binary BCH code of length 2m−1 and designed distance d:=2t+1 is defined as the cyclic binary code of length n:=2m−1 with roots α, α3, . . . , α2t−1 and their conjugates, where α is some primitive element in 2m*. BCH codes allow a precise control over the number of symbol errors correctable by the code during code design. In particular, it is possible to design binary BCH codes that can correct multiple bit errors. BCH codes can also be easily decoded using an algebraic method known as syndrome decoding. This can simplify the design of the decoder for these codes by using small, low-power electronic hardware.
The syndrome of a received codeword y=x+e, where x is the transmitted codeword and e is an error pattern, is defined in terms of a parity matrix H. A parity check matrix of a linear code C is a generator matrix of the dual code C⊥, which means that a codeword c is in C iff the matrix-vector product Hc=0. Then, the syndrome of the received word y=x+e is defined as S=Hy=H(x+e)=Hx+He=0+He=He. For the high-rate codes commonly used in practice, syndromes are useful in that the length of the syndrome, the codimension of the code, is much less than the length of the received word. For BCH codes, it is useful to work with a syndrome that corresponds to a particular parity-check matrix. For j∈{1, . . . , d−1}, let Sj:=y(αj), where for a field K and a vector f=(f0, f1, . . . fn−1)∈Kn, the vector f is identified with the polynomial f(X):=f0+f1X+ . . . +fn−1Xn−1∈K[X]. The syndrome polynomial associated with y is S(X):=S1+S2X+ . . . +Sd−1Xd−2. In terms of syndromes, the main computation in decoding binary BCH codes is to determine polynomials ω(X), σ(X)∈2m[X], that satisfy the following equation, known as a key equation:ω=Sσ mod X2t,where S is the syndrome polynomial, X is a free variable in the polynomial, ω(X)∈2m[X] is the error evaluator polynomial, defined by ω(X):=Σi=1∈αiΠj≠i (1+αjX), σ(X)∈2m[X] is the error locator polynomial defined by σ(X):=Πi=1∈(1+αiX), α is the primitive element in 2*m that was used to define the roots of the BCH code, ∈ is the actual number of hard-decision errors, α1, . . . , α∈ are the error locations, that is, field elements pointing to the location of the errors, and t is the designed decoding radius of the BCH code.
The Berlekamp-Massey (BM) algorithm is an algorithm for decoding BCH codes that finds an estimated error locator polynomial (ELP) C(X)=1+C1X+C2X2+ . . . +CLXL which results in zero coefficients for Xk in S(X)C(X) for k=L, . . . , 2t−1[S]k+C1[S]k−1+ . . . +CL[S]k−L=0, where L is the number of errors found by the algorithm, N=d−1=2t is the total number of syndromes, [S]i=Si+1 is the coefficient of Xi in the syndrome polynomial S(X) for all i, and k is an index that ranges from L to (N−1).
The BM algorithm begins by initializing C(X) to 1, L to zero; B(X) (a copy of the last C(X) since L was updated) to 1, b (a copy of the last discrepancy d since L was updated and initialized) to 1; and m (the number of iterations since L, B(X), and b were updated and initialized) to 1. The algorithm iterates from k=0 to N−1. At each iteration k of the algorithm, a discrepancy d is calculated:d=[S]k+C1[S]k−1+ . . . +CL[S]k−L.If d is zero, C(X) and L are assumed correct for the moment, m is incremented, and the algorithm continues.
If d is not zero and 2L>k, C(X) is adjusted so that a recalculation of d would be zero:C(X)=C(X)−(d/b)XmB(X).
The Xth term shifts B(X) to follow the syndromes corresponding to b. If the previous update of L occurred on iteration j, then m=k−j, and a recalculated discrepancy would be:d=[S]k+C1[S]k−1+ . . . −(d/b)([S]j+B1[S]j−1+ . . . ).This would change a recalculated discrepancy to: d=d−(d/b)b=d−d=0. Then, m is incremented, and the algorithm continues.
On the other hand, if d is not zero and 2L≤n, a copy of C is saved in vector T, C(X) is adjusted as above, B is updated from T, L is reset to (k+1−L), the discrepancy d is saved as b, m is reset to 1, and the algorithm continues.
A Chien search is an algorithm for determining roots of polynomials over a finite field, such as ELPs encountered in decoding BCH codes. Let α be a primitive element of a finite field with a multiplicative subgroup. Chien's search tests the non-zero elements in the field in the generator's order α1, α2, α3, . . . . In this way, every non-zero field element is checked. If at any stage the resultant polynomial evaluates to zero, then the associated element is a root.
Hard information for a received bit is the estimated bit value, i.e., 0 or 1, while “soft information” includes both an estimated value and the reliability of this estimation. This reliability may take many forms, but one common form is the probability, or an estimation of this probability, that the estimation is correct. For example, in the case of a single-level cell (SLC) flash memory, in which each cell stores a single bit, hard information is obtained with a single read (single threshold), while increasingly refined soft information is obtained from additional reads.
In hard-decision (HD) decoding, the hard-information vector (per-coordinate bit estimates) is used as the input of an error-correcting code (ECC) decoder, while in soft-decision (SD) decoding, a soft information vector (per-coordinate reliability vector on top of the hard-information vector) is used as the input of the ECC decoder.
Thus, soft information may be regarded as an estimate of the reliability of each bit estimate, on top of the bit estimates themselves. Hence, bits with a high enough reliability may be considered “strong”, while the remaining bits may be considered “weak”. For example, in an SLC flash memory, one read, e.g., with threshold level h, results in the HID vector, while two additional reads, e.g., with thresholds h+Δ, h−Δ, may be used to divide bits into strong and weak bits.
Chase decoding is a simple SD decoding algorithm for a code having only an HD decoding block, such as a BCH code. In Chase decoding, if an HD decoding fails, soft information is used to divide the received bits into strong, i.e., reliable, and weak, i.e., unreliable, bits. Suppose there are R weak bits. Some patterns of weak-bits flips are tested, such as all possible 2R flipping possibilities. For each flipping pattern, HD decoding is used. If, for some flipping pattern, the number of post-flipping errors is less than t, the HD correction radius of the code, then the decoding is said to have succeeded.
Now consider binary BCH codes. These codes are widely used in NAND flash applications, both for themselves, and as component codes in generalized concatenated codes. In a conventional Chase decoder, for each tested flipping pattern, a full HD decoder is invoked. This involves a syndrome computation, invoking the BM algorithm to find the ELP, and a Chien search to find the roots of the ELP.
However, if, in moving from pattern i to pattern i+1, a single additional bit is flipped, is it necessary to run a full HD decoder for pattern i+1? One answer is the Welch-Berlekamp (WB) algorithm, which is an interpolation-based fast Chase decoding. The WB algorithm differs from the BM algorithm in that while the BM algorithm starts by calculating syndromes from the received word and then works only with the syndromes, the WB algorithm works directly on the received word. Note that for high-rate codes that are used in flash memories, it is more efficient to work with syndromes, because the total length (in bits) of all syndromes is much smaller than the total length of the received word. Hence, in this case it is worth converting the received word into syndromes once and for all at the beginning of decoding, and then to continue processing only the small syndromes. In addition, entirely replacing an existing BM-based HD decoder by a Welch-Berlekamp decoder is non-trivial, and for high-rate codes, to reduce the complexity of the Welch-Berlekamp algorithm to that of the BM algorithm, it is necessary to use a re-encoding transformation, which requires a new hardware design for the core HD decoder.
Another answer is Wu's algorithm, “Fast Chase Decoding Algorithms and Architectures for Reed-Solomon Codes”, IEEE Transactions on Information Theory, Vol. 58, No. 1, January 2012, pgs. 109-129, the contents of which are herein incorporated by reference in their entirety, which is a BM-based fast Chase decoding. In Wu's method, for each additional flipped bit, a calculation similar to the last step of the BM algorithm is performed, instead of the full BM algorithm, and a syndrome re-calculation is not required. Note that a conventional decoder uses the Berlekamp-Massey (BM) algorithm in each trial, so the number of finite field multiplications in the BM algorithm is O(t2), where t is defined above. In Wu's method, one can use the previous estimation of the ELP to obtain the next estimation in O(t) finite field multiplications. So, instead of naively re-running the BM algorithm, one uses the previous result to save time. Thus, each step is linear in t, instead of quadratic in t. In particular, in Wu's algorithm, each additional flipped bit requires two discrepancy calculations and two polynomial updates. However, the manipulated polynomials typically have a degree that grows from t to the actual number of errors, say, t+r.
Wu also has a heuristic stopping criterion for entering the Chien search. Note that a stopping criterion must never miss the correct error locator, but is allowed to have (rare) false positives. A false positive is just an unnecessary computation. If these unnecessary computations are rare, then they have practically no effect. Wu's stopping criterion never misses the correct error-locator polynomial, and rarely has a false positive, but does result in a small degradation in frame-error rate (FER) as compared to full Chien search.